Решето Эратосфена

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n. Сложность алгоритма равна O(nlog(logn)).

Суть алгоритма заключается в том, чтобы поэтапно исключать из набора чисел от 2 до n числа, делящиеся на 2(кроме 2), 3(кроме 3), 5(кроме 5) и так далее. Мы не будем искать числа, которые делятся на 4, 6, 8, 9 и так далее, потому что мы их уже исключили ранее.

Реализация

Для реализации алгоритма нам понадобится массив размера n. Индекс массива будет равен числу, а значение массива с этим индексом будет определять простое число или нет. Изначально инициализируем все элементы массива как простые числа. Далее начинаем поэтапно исключать составные числа, которые делятся на i. В строке 12 мы начинаем с i * i, так как до значения i * i мы уже отобрали простые числа. Допустим i = 5, тогда j может принимать значения от 10 до n с шагом 5, но нам не нужно проверять числа 2 * 5, 3 * 5, 4 * 5, так как мы их уже исключили когда i было равно 2, 3 и 4 соответственно. Другими словами все меньшие числа, кратные i, обязательно имеют простой делитель меньше i, а они уже исключены к этому времени. Так как минимальное исключенное число для i будет i * i, то внешний цикл делаем с границей i < sqrt(n) или i * i < n.

Код на Си:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
int main() {
	int n, i, j, k;
	int A[1000] = { 0 };
	scanf("%i", &n);
	for (i = 2; i * i <= n; i++) {
		if (A[i] == 0) {
			for (j = i * i; j <= n; j += i) {
				A[j] = 1;
			}
		}
	}
	for (i = 2; i <= n; i++) {
		if (A[i] == 0) {
			printf("%i ", i);
		}
	}
	return 0;
}

Данный алгоритм выводит все простые числа от 2 до n включительно.

Для лучшего понимания можете посмотреть видео Тимофея Хирьянова на Ютубе.